package com.example.zz.example.datastructures;


import java.util.LinkedList;

/**
 * 链表基础概念：
 *
 * 在java中要实现一个链表，需要自定义表示链表的类如下面的Node类，来模拟这种数据结构。
 * Node类是一个最简单的链表类，item表示这个链表结点中存储的数据，next 指向下一个链表节点。每当new一个Node实例，在内存中就会为其分配内存空间，
 * 它就会有一个内存地址。next就是用来存放下一个结点的内存地址的。还可以扩展各类方法
 *
 * java中的LinkedList是基于双向循环链表实现的链表。为了好用，还添加了Serializable接口支持序列化，
 * 还实现了Queue等接口，可以当做栈、队列和双端队列来进行使用，所以java中的LinkedList是一个功能集合的大杂烩。
 */
public class LinkedListDemo {
    public static void main(String[] args) {

        ListNode<String> head = new ListNode<>("node 1");
        ListNode<String> listNode2 = new ListNode<>("node 2");
        ListNode<String> listNode3 = new ListNode<>("node 3");
        head.next = listNode2;
        listNode2.next = listNode3;

        //顺序遍历
        ListNode<String> current = head;
        while (current != null) {
            System.out.println(current.item);
            current = current.next;
        }

        //倒序遍历
        printListRev(head);

        ListNode<String> head4 = new ListNode<>("head4");
        ListNode<String> head5 = new ListNode<>("head5");
        head4.next = head5;
        head5.item = "headx";
        head4 = head4.next;
        System.out.println(head5.item); //"headx"
        System.out.println(head4.item); //"headx"


        ListNode<String> head6 = new ListNode<>("head6");
        ListNode<String> head7 = new ListNode<>("head7");
        head6.next = head7;

        ListNode<String> result;
        result = head6;
        head6 = head6.next;

        System.out.println(head6.item); //"head7"
        System.out.println(result.item); //"head6"   ???

    }

    public static void printListRev(ListNode<String> head) {
        //倒序遍历链表主要用了递归的思想
        if (head != null) {
            printListRev(head.next);
//            if (head.next != null){
//                if (head.next.next != null){
//                    if (head.next.next.next != null){
//                        //...
//                        System.out.println(head.next.item);
//                    }
//                    System.out.println(head.next.next.item);
//                }
//                System.out.println(head.next.item);
//            }
            System.out.println(head.item);
        }
    }


    public static class ListNode<E> {
        E item;
        ListNode<E> next;

        public ListNode(E e) {
            item = e;
            next = null;
        }
    }
}
